package Algorithm.dfs;

/**
 * 695. 岛屿的最大面积 https://leetcode.cn/problems/max-area-of-island/
 */
public class MaxAreaOfIsland {

    /**
     * 岛屿系列问题2
     * dfs解法
     */
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int i = 0;i < grid.length;i++) {
            for(int j = 0;j < grid[0].length;j++) {
                if(grid[i][j] == 1) {
                    int area = dfs(i, j, grid);
                    if(area > max) max = area;
                }
            }
        }
        return max;
    }

    /**
     * dfs遍历计算一座岛屿的面积
     * 岛屿面积等于1加上网格上下左右陆地的面积
     */
    public int dfs(int i, int j, int[][] grid) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length)
            return 0;
        if(grid[i][j] != 1)
            return 0;
        grid[i][j] = 2;
        int up = dfs(i-1, j, grid);
        int down = dfs(i+1, j, grid);
        int left = dfs(i, j-1, grid);
        int right = dfs(i, j+1, grid);
        return 1+up+down+left+right;
    }
}
